package 实现数据结构.实现动态数组;


/**
 * @DESC 散列表的实现示例
 * @Author tzq
 * @Date 2019-10-06 17:32
 **/
public class HashTable {
    /**
     * 初始大小，可以自由设置
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 4;
    private static final float LOAD_FACTOR = 0.75f;

    /**
     * 散列表数组
     **/
    private Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY];
    private int size = 0;
    private int use = 0;

    /**
     * 添加元素
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new Entry(-1, -1, null);
        }
        Entry e = table[index];
        if (e.next == null) {
            // 不存在的值，向链表添加有可能扩容，需要table属性
            table[index].next = new Entry(key, value, null);
            size++;
            use++;
            // 不存在的值，未用过需要判断是否需要扩容
            if (use > table.length * LOAD_FACTOR) {
                resize();
            }
        } else {
            // 本身已经存在则修改已有的值
            for (e = e.next; e != null; e = e.next) {
                int k = e.key;
                if (k == key) {
                    e.value = value;
                    return;
                }

            }
            //若不存在相同的值则直接向链表中添加元素
            Entry temp = table[index].next;
            Entry newEntry = new Entry(key, value, temp);
            table[index].next = newEntry;
            size++;

        }


    }

    /**
     * 查找元素
     *
     * @param key
     * @return
     */
    public int get(int key) {
        int index = hash(key);
        Entry e = table[index];
        if (e != null && e.next != null) {
            for (e = e.next; e != null; e = e.next) {
                int k = e.key;
                if (k == key) {
                    return e.value;
                }
            }
        }
        //没有找到
        return -1;
    }

    /**
     * 删除元素（更改链表指向即可）
     *
     * @param key
     */
    public void remove(int key) {
        int index = hash(key);
        Entry e = table[index];
        Entry pre = table[index];

        if (e != null && e.next != null) {
            for (e = e.next; e != null; pre = e, e = e.next) {
                int k = e.key;
                if (k == key) {
                    pre.next = e.next;
                    size--;
                    return;

                }
            }
        }


    }


    /**
     * 扩容
     */
    private void resize() {
        int newLength = table.length * 2;
        Entry[] oldTable = table;
        table = new Entry[newLength];
        use = 0;
        for (int i = 0; i < oldTable.length; i++) {
            if (oldTable[i] != null && oldTable[i].next != null) {
                Entry e = oldTable[i];
                while (null != e.next) {
                    Entry next = e.next;
                    //重新计算hash并放入新的地址当中
                    int index = hash(next.key);
                    if (table[index] == null) {
                        use++;
                        table[index] = new Entry(-1, -1, null);
                    }
                    Entry temp = table[index].next;
                    Entry newEntry = new Entry(next.key, next.value, temp);
                    table[index].next = newEntry;
                    e = next;
                }
            }
        }

    }

    /**
     * hash计算
     *
     * @param key
     * @return
     */
    private int hash(int key) {
        return key % table.length;
    }


    public int getLength() {
        return table.length;
    }

    public int szie() {
        return size;
    }
}
